12.11 Prüfsummen 

Damit Fehler bei Dateien oder bei Übertragungen von Daten auffallen, werden vor der Übertragung Prüfsummen (engl. checksum) gebildet und mit dem Paket versendet. Der Empfänger berechnet diese Prüfsumme neu und vergleicht sie mit dem übertragenen Wert. Stimmt der berechnete Wert mit dem übertragenen überein, so war die Übertragung höchstwahrscheinlich in Ordnung. Es sollte ziemlich unwahrscheinlich sein, dass eine Änderung einzelner Bits nicht auffällt. Prüfsummen erkennen auch beschädigte Archive. Pro Datei wird eine Prüfsumme berechnet. Soll die Datei entpackt werden, so errechnen wir wieder die Summe. Ist diese fehlerhaft, muss auch die Datei fehlerhaft sein. (Wir wollen hier ausschließen, dass zufälligerweise die Prüfsumme fehlerhaft ist, was natürlich ebenfalls der Fall sein kann.)

12.11.1 Die Schnittstelle Checksum 

Wir finden Zugang zur Prüfsummenberechnung über die Schnittstelle java.util.zip. Checksum, die für ganz allgemeine Prüfsummen steht. Eine Prüfsumme wird entweder für ein Feld oder ein Byte berechnet. Checksum liefert die Schnittstelle zum Initialisieren und Auslesen von Prüfsummen, die die konkreten Prüfsummen-Klassen implementieren müssen.

interface java.util.zip.Checksum

• long getValue() Liefert die aktuelle Prüfsumme.

• void reset() Setzt die aktuelle Prüfsumme auf einen Anfangswert.

• void update( int b ) Aktualisiert die aktuelle Prüfsumme mit b.

• void update( byte[] b, int off, int len ) Aktualisiert die aktuelle Prüfsumme mit dem Feld.

Die Standardbibliothek bietet bisher zwei Klassen für die Prüfsummenberechnung als Implementierungen von Checksum!

• java.util.zip.CRC32. CRC32 basiert auf einer zyklischen Redundanzprüfung und testet etwa Zip-Archive oder PNG-Grafiken.

• java.util.zip.Adler32. Die Berechnung von CRC32-Prüfsummen kostet – obwohl in C programmiert – viel Zeit. Eine Adler32-Prüfsumme kann wesentlich schneller berechnet werden und bietet ebenso eine geringe Wahrscheinlichkeit, dass Fehler unentdeckt bleiben.

12.11.2 Die Klasse CRC32 

Oft sind Polynome die Basis der Prüfsummenberechung. Eine häufig für Dateien verwendete Prüfsumme ist CRC32, und das bildende Polynom lautet:

Nun lässt sich zu einer 32-Bit-Zahl eine Prüfsumme berechnen, die genau für diese vier Bytes steht. Damit bekommen wir aber noch keinen ganzen Block kodiert. Um das zu erreichen, berechnen wir den Wert eines Zeichens und Xor-verknüpfen den alten CRC-Wert mit dem neuen. Jetzt lassen sich beliebig Blöcke sichern. Die Berechnung ist insgesamt sehr zeitaufwändig, und Adler32 stellt eine schnellere Alternative dar.

CRC32 crc = new CRC32(); 
byte[] ba = new byte[ (int)in.available() ]; 
in.read( ba ); 
crc.update( ba ); 
in.close();

CRC32 implementiert nicht nur alle Methoden, sondern fügt noch zwei Funktionen und natürlich einen Konstruktor hinzu.

class java.util.zip.CRC32 
implements Checksum

• CRC32() Erzeugt ein neues CRC32-Objekt mit der Start-Prüfsumme 0.

• long getValue() Liefert den CRC32-Wert.

• void reset() Setzt die interne Prüfsumme auf 0.

• void update( byte[] b ) Aktualisiert die Prüfsumme mit dem Feld durch Aufruf von update(b, 0, b.length).

• void update( int b ) Implementiert update() aus Checksum für ein Byte. Nativ implementiert.

• void update( byte[] b, int off, int len ) Implementiert update() aus Checksum für ein Feld. Nativ implementiert.

CRC eines Datenstroms berechnen

Eine Möglichkeit, die CRC32 eines Datenstroms zu berechnen, bestünde darin, einen Datenstrom entgegenzunehmen und anschließend so lange Byte-Folgen auszulesen, bis available() null liefert. An diesem Punkt lässt sich mit update() jeweils die Prüfsumme korrigieren. Bei großen Dateien ist es sicherlich angebracht, Blöcke einzulesen, die crc.update(byte[]) verarbeitet. Für diese Aufgabe verfügt die Java-Bibliothek über zwei Filter-Klassen: CheckedInputStream und CheckedOutputStream. Beide sind Filter, die existierende andere Streams ummanteln und gleichzeitig die Berechnung erledigen.

Listing 12.32    com/javatutor/insel/io/CRC32Demo.java, main()

InputStream in = CRC32Demo.class.getResourceAsStream( "/lyrics.txt" ); 
try 
{ 
  CRC32 crc = new CRC32(); 
  InputStream cis = new CheckedInputStream( in, crc ); 
 
  while ( cis.read() != -1 ) { /* Bis Ende lesen. */ } 
  System.out.printf( "%X", crc.getValue() ); 
} 
catch ( IOException e ) { 
  e.printStackTrace(); 
} 
finally { 
  try { in.close(); } catch ( Exception e ) { } 
}

12.11.3 Die Adler32-Klasse 

Der Algorithmus ist nach seinem Programmierer Mark Adler benannt und stellt eine Erweiterung des Fletcher [Fletcher, J. G., »An Arithmetic Checksum for Serial Transmissions«. IEEE Transactions on Communications, Ausgabe. COM-30, Nummer. 1, Januar 1982, Seite 247 – 252. ] -Algorithmus dar. Der Adler32-Algorithmus ist im ITU-T X.224/ISO 8073-Standard definiert und gilt für 32-Bit-Zahlen. Die Adler32-Prüfsumme setzt sich aus zwei Summen für ein Byte zusammen. s1 ist die Summe aller Bytes und s2 die Summe aller s1. Beide Werte werden Modulo 65521 genommen. Am Anfang ist s1 = 1 und s2 = 0. Die Adler32-Prüfsumme speichert den Wert als s2 * 65536 + s1 in der MSB-Reihenfolge (Most-Significant-Byte First, Netzwerkreihenfolge).

Eine Beschreibung der Kompression und des Adler32-Algorithmus findet sich im Internet-Draft »ZLIB Compressed Data Format Specification version 3.3«.

class java.util.zip.Adler32 
implements Checksum

• Adler32() Erzeugt ein neues Adler32-Objekt mit der Start-Prüfsumme 1.

• long getValue() Liefert den Adler32-Wert.

• void reset() Setzt die interne Prüfsumme auf 1.

Aus der Schnittstelle Checksum implementiert Adler32 natürlich auch die update()-Methoden.